传送门：https://codeforces.com/contest/1619

A. Square String?

对半匹配

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined  */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,a[2*N];
string str;

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //  -DLOCAL
        freopen("in.in", "r", stdin);
    #endif
    cin >> _;
    while(_--){
        cin >> str;
        n = str.length();
        if(n%2){
            cout << "NO\n";
            continue;
        } else {
            bool flag = true;
            rep(i,1,n/2){
                if(str[i-1] == str[i-1+n/2]) continue;
                flag = false;
                break;
            }
            if(flag) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}

---

B. Squares and Cubes

找1~n中完全平方数或者完全立方数的数量，先预处理所有完全平方数数组和完全立方数数组。

然后遍历小于n的完全立方数数量cnt1，找到其中也是完全平方数的数量cnt2，再找到所有小于n的完全平方数数量cnt3，显然，答案就是cnt1 + cnt3 - cnt2。

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined  */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,a2[2*N],l2,a3[2*N],l3;
std::set<int> s3,s2;

void init(){
    rep(i,1,inf){
        if(i * i >= inf) break;
        a2[++l2] = i*i;
        s2.insert(i*i);
    }
    rep(i,1,inf){
        if(i * i * i >= inf) break;
        a3[++l3] = i*i*i;
        // s3.insert(i*i*i);
    }
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //  -DLOCAL
        freopen("in.in", "r", stdin);
    #endif
    cin >> _;
    init();
    while(_--){
        cin >> n;
        int cnt = 0;
        rep(i,1,l3){
            if(a3[i] <= n) ++cnt;
            // if(a3[i] <= n) cout << a3[i] << "\n";
            if(a3[i] <= n && s2.find( a3[i] ) != s2.end()) --cnt;
        }
        rep(i,1,l2){
            if(a2[i] <= n) ++cnt;
            // if(a2[i] <= n) cout << a2[i] << "\n";
        }
        cout << cnt << "\n";
    }
    return 0;
}

---

C. Wrong Addition

实际上就是把进位分离出来的一个竖式加法，我们要去做这种模式下的一个减法。那做法就很简单了，减出负数就进位就可以了。

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined  */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,lenA,lenS,b[2*N],a[2*N],s[2*N];
string A,S;

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //  -DLOCAL
        freopen("in.in", "r", stdin);
    #endif
    cin >> _;
    while(_--){
        cin >> A >> S;
        lenA = A.length() , lenS = S.length();
        rep(i,0,lenA-1) a[lenA-i] = A[i] - '0';
        rep(i,0,lenS-1) s[lenS-i] = S[i] - '0';
        rep(i,0,lenS+1) b[i] = 0; 
        int j = 1 , i = 1 , p;
        bool ans = true;
        while(1){
            p = i;
            if(j > lenS) break;
            if(i > lenA) a[i] = 0;
            if(s[j] >= a[i]){
                b[i] = s[j] - a[i];
                j += 1;
            } else{
                if(s[j+1] > 1 || s[j+1] < 1){
                    ans = false;
                    break;
                }
                b[i] = s[j] + s[j+1] * 10 - a[i];
                j += 2;
            }
            ++i;
        }
        if(!ans || i <= lenA){
            cout << "-1\n";
            continue;
        }
        bool leadZero = true;
        bool isZero = true;
        per(i,p,1){
            if(b[i]) leadZero = false;
            else if(leadZero) continue;
            cout << b[i];
            isZero = false;
        }
        if(isZero) cout << "-1";
        cout << "\n";
    }
    return 0;
}

---

D. New Year’s Problem

You can get English version here.

官方给出的解法是二分答案，但是我在评论区看到一个更有意思的解法，公式如下：

$$ans = min\{ minTop1ByFriends , maxTop2ByShops \}$$

解释如下：

根据题意，首先容易得到 $ans \leq minTop1ByFriends$​

规定a[i][j]表示礼物j对人i的贡献

1. 让我们先假设$n-1 \leq m$​

• 下面给出一个买礼物的策略：

  • 选择某一个人I，找到他最喜欢的礼物J，并且先假设a[I][J] = max{ a[1][J] , a[2][J] , ... , a[n][J] }（即这个礼物最被I喜欢），我们称之为假设A

  • 找到a[1][J] , a[2][J] , ... , a[n][J]中的次大项（Top2），并找到该对应的I'，于是已经有2个人的礼物被安排好了

    • 这两个人的joy分别是top1ByFriends[I]和top2ByShops[J]

  • 对于剩下的n-2个人，必定能找到他们最喜欢的礼物

    • 对于这些人，他们的joy分别是top1ByFriends[i]
  • 不难得到，在这种策略下，遍历所有的“某一个人I”，可以证明，对于某一个确定的I，在假设A成立的情况下，这种策略是可行的，而在这些所有策略里找最大值，容易得到$ans\leq maxTop2ByShops$​​。​
  • 现在我们来考虑假设A不成立的情况，显然，这种情况不影响我们的结论，因为此时top1ByFriends[I]<top2ByShops[J]，答案就主要由top1ByFriends[I]决定，我们不再需要关心I'到底是否是次大还是最大，只要比I的大就行了

• 所以

  $$ans \leq min\{minTop1ByFriends , maxTop2ByShops \}$$

• 我们再来看取等问题

  • 当$minTop1ByFriends \leq maxTop2ByShops$时，我们取I为这个取到minTop1ByFriens的I，按照上述策略，可取等
  • 当$minTop1ByFriends \geq maxTop2ByShops$时，我们取J为这个取到maxTop2ByShops的J，并选取该J对应的Top1ByShops对应的I，按照上述策略，可取等

• 所以可以取等，所以

  $$ans = min\{ minTop1ByFriends , maxTop2ByShops \}$$

1. 对于$n-1> m$的情况，我在这里做了详细解释

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined  */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,m,a[2*N],minTop1ByFriends,maxTop2ByShops,top1ByFriends[2*N],top2ByShops[2*N];

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //  -DLOCAL
        freopen("in.in", "r", stdin);
    #endif
    cin >> _;
    while(_--){
        cin >> m >> n;
        rep(j,1,m) rep(i,1,n) cin >> a[(i-1)*m + (j-1)];
        minTop1ByFriends = inf , maxTop2ByShops = 0;
        rep(i,1,n){
            top1ByFriends[i] = 0;
            rep(j,1,m){
                if(a[ (i-1)*m + (j-1) ] > top1ByFriends[i]) top1ByFriends[i] = a[ (i-1)*m + (j-1) ];
            }
        }
        rep(j,1,m){
            int tmpMax = j-1;
            rep(i,1,n){
                if(a[ (i-1)*m + (j-1) ] > a[tmpMax]) tmpMax = (i-1)*m + (j-1);
            }
            top2ByShops[j] = 0;
            rep(i,1,n){
                if((i-1)*m + (j-1) == tmpMax) continue;
                if(a[ (i-1)*m + (j-1) ] > top2ByShops[j]) top2ByShops[j] = a[ (i-1)*m + (j-1) ];
            }
        }
        minTop1ByFriends = inf;
        rep(i,1,n){
            minTop1ByFriends = std::min(minTop1ByFriends,top1ByFriends[i]);
        }
        maxTop2ByShops = 0;
        rep(j,1,m){
            maxTop2ByShops = std::max(maxTop2ByShops,top2ByShops[j]);
        }
        // cout << "debug::  " << minTop1ByFriends << "   " << maxTop2ByShops << "  \n";
        cout << std::min(minTop1ByFriends,maxTop2ByShops) << "\n";
    }
    return 0;
}

---

E. MEX and Increments

1.首先解决有没有策略的问题

只要存在至少k个小于k的数，就可以实现MEX = k，对于等于k的这些要通过把他们变大来让他们都不等于k

2.解决最优策略的问题

很容易理解可以通过递推实现，假设实现MEX = k-1最少需要p步，其中由q步用来将等于k-1的数变成k（即原数列中存在q个等于k-1的数），q >= 0，等于k的数一共由q'个（即需要q'步来让它们变成k+1），那么实现MEX = k所需要的最少的步骤数即为p - q + q' + delP，其中：

• 如果q = 0，delP为最大的空闲的数
• 如果q > 0，delP = 0

而所谓的空闲的数，就是在实现MEX = k-1后还剩下的多余的小于k-1的数

注意优化查找空闲的数这个步骤

Code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined  */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,a[2*N],less[2*N],equal[2*N],stack[2*N],top;
ll ans;


int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //  -DLOCAL
        freopen("in.in", "r", stdin);
    #endif
    cin >> _;
    while(_--){
        cin >> n;
        rep(i,1,n) cin >> a[i];
        std::sort(a+1,a+n+1,cmp);
        rep(i,0,n+10) less[i] = equal[i] = stack[i] = 0;
        top = 5;
        int p = 1;
        rep(i,0,n){
            if(i > 0) less[i] += equal[i-1] + less[i-1];
            while(p <= n && a[p] < i) ++less[i],++p;
            while(p <= n && a[p] == i) ++equal[i],++p;
            // cout << less[i] << " ; ";
        }
        // cout << "\n";
        bool unable = false;
        ans = 0;
        rep(i,0,n){
            if(unable){
                cout << "-1 ";
            } else if(less[i] < i){
                unable = true;
                cout << "-1 ";
            } else {
                if(i == 0) ans = equal[0];
                else {
                    // cout << "debug :: " << ans << " " << equal[i-1] << " " << equal[i] << " ";
                    if(i > 1){
                        if(equal[i-2] > 1) stack[++top] = i-2;
                    }
                    ans -= equal[i-1];
                    ans += equal[i];
                    if(equal[i-1] == 0){
                        --equal[ stack[top] ];
                        ans += i-1 - stack[top];
                        if(equal[ stack[top] ] <= 1) --top;
                    }
                }
                cout << ans << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}